package test;

/**
 * @author sunzhuokun
 * @date 11:14 2024/5/16
 * @description 二叉树的广度优先遍历
 * 题目描述
 *
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和
 * 中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果。
 *
 *  输入
 *
 * 每个输入文件包含两串字母，各占一行。（每串只包含大写字母）
 * 第一行字母表示前序遍历结果，第二行字母表示中序遍历结果。
 * 输出
 *
 * 输出仅一行，表示后序遍历的结果，结尾换行。
 * 样例
 *
 * 输入样例 1
 *
 * DBACEGF
 * ABCDEFG
 *
 * 输出样例 1
 *
 * ACBFGED
 *
 * 提示样例 1
 *
 * 提示
 *
 * 前序遍历：根—>左孩子—>右孩子
 * 中序遍历：左孩子—>根—>右孩子
 * 后序遍历：左孩子—>右孩子—>根
 * 所谓的前中后指的是根的位置，而左右孩子顺序是不变的。
 *
 * 例如已知前序遍历是DBACEGF，中序遍历是ABCDEFG，那么由前序遍历先根，可知道D是树的根，再看在中序遍历中D左边是ABC，所以可知道ABC一定在D的左子树上，而EFG在D的右子树上。
 * 那么前序遍历为BAC,中序遍历为ABC，所以B为根，在中序遍历中A在B的左边，C在B的右边，所以A为B的左孩子，C为B的右孩子。
 * 思路：先从先序遍历中找到根节点，然后从中序遍历中找到左子树和右子树，递归，构建二叉树，最后再进行后序遍历。
 */
public class BreadthFirstTraversalOfBinaryTree_二叉树的广度优先遍历 {

    public static void main(String[] args) {
        String preOrder = "DBACEGF";
        String inOrder = "ABCDEFG";
        TreeNode root = buildTree(preOrder, inOrder);
        lastOrder(root);
    }

    private static void lastOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        lastOrder(node.left);
        lastOrder(node.right);
        System.out.print(node.val);
    }

    /**
     * 根据中序和先序结果构建二叉树
     * @param preOrder
     * @param inOrder
     * @return
     */
    private static TreeNode buildTree(String preOrder, String inOrder) {
        if (preOrder == null || preOrder.length() == 0) {
            return null;
        }
        char minVal = preOrder.charAt(0);
        TreeNode root = new TreeNode(minVal);
        // 只剩根节点，结束
        if (preOrder.length() == 1) {
            return root;
        }

        // 寻找下一级节点跟节点位置
        int midIndex = 0;
        for (; midIndex < preOrder.length(); midIndex++) {
            if (midIndex == inOrder.indexOf(minVal)) {
                break;
            }
        }

        String preLeft = preOrder.substring(1, midIndex + 1);
        String preRight = preOrder.substring(midIndex + 1);

        String inLeft = inOrder.substring(0, midIndex);
        String inRight = inOrder.substring(midIndex + 1);

        root.left = buildTree(preLeft, inLeft);
        root.right = buildTree(preRight, inRight);

        return root;
    }

    static class TreeNode {
        char val;

        TreeNode left;

        TreeNode right;

        // 构造器
        TreeNode(char val) {
            this.val = val;
        }
    }

}
